//
//  Hot100.swift
//  SFQuestion
//
//  Created by liusr on 2022/2/15.
//

import Foundation

// 热题100

class SolutionHot {
    
    //300. 最长递增子序列
    // #动态规划
    func lengthOfLIS(_ nums: [Int]) -> Int {
        // https://labuladong.gitee.io/algo/3/24/79/
        // dp[i]：以nums[i]为结尾的最长递增子序列的长度。。。这句话蕴含了好几个步骤
        // dp的含义要熟记于心，关系到理解代码的递推关系
        if nums.isEmpty {
            return 0
        }
        var dp = Array.init(repeating: 1, count: nums.count)//初值1
        for i in 0..<nums.count {
            var temp = dp[i]
            for j in 0..<i {
                if nums[j] < nums[i] {
                    temp = max(temp, dp[j] + 1)
                }
            }
            dp[i] = temp
        }
                
        return dp.max() ?? 0
    }
    

    //MARK: 两数之和
    //遍历的时候把每一个位置的差值存下来，遍历到后面有差值是前面出现过得，说明相加就是target
    //存差值  判断的时候就是判断有没有当前的值。存当前的值 判断的时候就是判断差值
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var tmp = [Int:Int]()
        for (i, v) in nums.enumerated() {
            if let preIndex = tmp[v] {
                return [preIndex, i]
            } else {
                tmp[target - v] = i
            }
        }
        return [Int]()
    }
    
    //返回这俩数
    func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.isEmpty {
            return [Int]()
        }
        var p1 = 0
        var p2 = nums.count - 1
        //得先排序
        let sortNums = nums.sorted(by: <)
        print(sortNums)
        while p1 < p2 {
            let sum = sortNums[p1] + sortNums[p2]
            if sum < target {
                p1 = p1 + 1
            } else if sum > target {
                p2 = p2 - 1
            } else {
                //因为排序了 只能返回数字
                return [sortNums[p1], sortNums[p2]]
            }
        }
        return [Int]()
    }
    
    //239. 滑动窗口最大值
    /*
     给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

     返回 滑动窗口中的最大值 。
     输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
     输出：[3,3,5,5,6,7]
     */
    
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        
        let n = nums.count
        if k > n {
            return [Int]()
        }
        //创建一个索引队列，最大为k相当于窗口，存放nums的下标，而且保证这些索引对应的值是逐渐小的，保证对头最大值
        var res = [Int]()
        var deque = [Int]()
        
        for i in 0..<k {
            //窗口是移动的 == 要算进去
            while !deque.isEmpty && nums[i] >= nums[deque.last!] {
                deque = deque.dropLast()
            }
            deque.append(i)
        }
        //把第一个窗口值加进去
        if let index = deque.first {
            res.append(nums[index])
        }
        
        for i in k..<n {
            while !deque.isEmpty && nums[i] >= nums[deque.last!] {
                deque.removeLast()
            }
            deque.append(i)
            
            //左边超出窗口
            while deque.first! <= i-k {
                deque.removeFirst()
            }
            
            //取第一个索引
            if let index = deque.first {
                res.append(nums[index])
            }
        }
        
        return res
    }
    
    /*
     53. 最大子数组和
     给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

     子数组
     是数组中的一个连续部分。

      

     示例 1：

     输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     输出：6
     解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     */
    
    func maxSubArray(_ nums: [Int]) -> Int {
            if nums.isEmpty {
                return 0
            }
            
            var dp = nums[0]
            var res = nums[0]
            for i in 1..<nums.count {
                if dp < 0 {
                    dp = nums[i]
                } else {
                    dp = nums[i] + dp
                }
                res = max(res, dp)
            }
            return res
        }
    
    /*
     189 轮转数组
     给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

      

     示例 1:

     输入: nums = [1,2,3,4,5,6,7], k = 3
     输出: [5,6,7,1,2,3,4]
     解释:
     向右轮转 1 步: [7,1,2,3,4,5,6]
     向右轮转 2 步: [6,7,1,2,3,4,5]
     向右轮转 3 步: [5,6,7,1,2,3,4]

     我们可以通过三次翻转的方法来实现。步骤如下：

     翻转整个数组。
     翻转前 k 个元素。
     翻转剩余的元素。
     这个方法的时间复杂度为 O(n)，空间复杂度为 O(1)。
     
     */
    
    func rotate(_ nums: inout [Int], _ k: Int) {
        let count = nums.count
        if count == 0 {
            return
        }
        //取个余 因为k可能会超过长度
        var k = k % count
        nums.reverse()
        
        var i = 0
        var j = k - 1
        while i < j && i < count {
            nums.swapAt(i, j)
            i += 1
            j -= 1
        }
        
        i = k
        j = count - 1
        while i < j && k < count {
            nums.swapAt(i, j)
            i += 1
            j -= 1
        }
    }
    
    
    //94. 二叉树的中序遍历 力扣没过，但是写的没问题啊，测试例子通过
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var res = [Int]()
        self.inOrder(root, &res)
        return res
    }

    func inOrder(_ root: TreeNode?, _ res: inout [Int]) {
        if let node = root {
            self.inOrder(node.left, &res)
            res.append(node.val)
            self.inOrder(node.right, &res)
        }
    }

    /*
     回文链表
     class ListNode {
         var val: Int
         var next: ListNode?

         init(_ val: Int) {
             self.val = val
             self.next = nil
         }
     }

     func isPalindrome(_ head: ListNode?) -> Bool {
         guard head != nil && head?.next != nil else {
             return true
         }
         
         // Step 1: Find the middle of the linked list using slow and fast pointers
         var slow = head
         var fast = head
         
         while fast != nil && fast?.next != nil {
             slow = slow?.next
             fast = fast?.next?.next
         }
         
         // Step 2: Reverse the second half of the linked list
         var secondHalf = reverseList(slow)
         slow = nil  // Cut off the first half from the second half
         
         // Step 3: Compare the first half and the reversed second half
         var p1 = head
         var p2 = secondHalf
         
         while p1 != nil && p2 != nil {
             if p1?.val != p2?.val {
                 return false
             }
             p1 = p1?.next
             p2 = p2?.next
         }
         
         return true
     }

     func reverseList(_ head: ListNode?) -> ListNode? {
         var prev: ListNode? = nil
         var curr = head
         
         while curr != nil {
             let nextTemp = curr?.next
             curr?.next = prev
             prev = curr
             curr = nextTemp
         }
         
         return prev
     }
     回文链表
     
     */
    /*
     153题目
     已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

     给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素
     
     */
    func findMin(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return -1
        }
        var index = -1
        var left = 0, right = nums.count - 1
        while left < right {
            let mid = left + (right - left) / 2
            if nums[mid] >= nums[right] {
                left = mid + 1
            } else if nums[mid] < nums[right] {
                right = mid
            }
        }
        return left
    }
    
    /*
     20. 有效的括号
     
     给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

     有效字符串需满足：

     左括号必须用相同类型的右括号闭合。
     左括号必须以正确的顺序闭合。
     每个右括号都有一个对应的相同类型的左括号。
     
     */
    
    func isValid(_ s: String) -> Bool {

            var stack = [Character]()
            var characters = Array(s)
            for c in characters {
                switch c {
                    case "(", "{", "[":
                    stack.append(c)
                    case ")":
                    if stack.isEmpty || stack.removeLast() != "(" {
                        return false
                    }
                    case "}":
                    if stack.isEmpty || stack.removeLast() != "{" {
                        return false
                    }
                    case "]":
                    if stack.isEmpty || stack.removeLast() != "[" {
                        return false
                    }
                    default:
                    break
                }
            }
            return stack.isEmpty

        }
    
    
    /*
     394.字符串解码
     
     给定一个经过编码的字符串，返回它解码后的字符串。

     编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

     你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

     此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

      

     示例 1：

     输入：s = "3[a]2[bc]"
     输出："aaabcbc"
     示例 2：

     输入：s = "3[a2[c]]"
     输出："accaccacc"
     示例 3：

     输入：s = "2[abc]3[cd]ef"
     输出："abcabccdcdcdef"
     示例 4：

     输入：s = "abc3[cd]xyz"
     输出："abccdcdcdxyz"
     
     */
    //做的不对 太麻烦了 来回匹配
    func decodeString(_ s: String) -> String {
        var res = ""
        var stringArr:[Character] = Array(s)
        var stack = [String]()
        var nums = ""
        for character in stringArr {
            let num:UInt8 = character.asciiValue ?? 0
            
            if character == "[" {
                //遇到这个就可以把数字加进去了
                stack.append(nums)
                nums = ""
                stack.append("[")
            } else if character == "]" {
                
                var subString = ""
                while !stack.isEmpty {
                    var ch = stack.removeLast()
                    if ch == "[" {
                        var num = stack.removeLast()
                        for _ in 0..<(Int(num) ?? 0) {
                            res += subString.reversed()
                        }
                        break
                    }
                    subString += ch
                }
                
                
            } else if num >= 48, num <= 57  {
                nums = nums + String(character)
            } else {
                stack.append(String(character))
            }
            
            
        }
        return res
    }
    
    //739每日温度
    
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
            //暴力循环超时 只能考虑遍历一次  用一个单调栈 栈里面只放温度递减的值的 下标
            var res = Array(repeating: 0, count: temperatures.count)
            //swift可以放元祖，一个是下标 一个是对应值
            var stack = [(Int, Int)]()
            for (i, value) in temperatures.enumerated() {
                
                while !stack.isEmpty, value > stack.last!.1 {
                    res[stack.last!.0] = i - stack.last!.0
                    stack.removeLast()
                }
                
                stack.append((i, value))
            }
            return res
        }
    
    
    /*
     215. 数组中的第K个最大元素

     给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

     请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

     你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     
     第k大， 注意是倒着数
     比如 排序号的数组是
     123456  第2大 就是 5的位置 下标是4 = 数组个数6 - 2 = 4
     第3 大 就是4的位置  3 = 6 - 3 下标 3
     
     */

    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        return quickSelect(&nums, 0, nums.count - 1, nums.count - k)
    }

    func quickSelect(_ nums: inout [Int], _ left: Int, _ right: Int, _ k: Int) -> Int {
        if left == right {
            //这个注释掉其实可以  下面肯定会有一个中枢等于k的
            return nums[left]
        }
        //这里就是中枢函数 用快排的就行
        let pivotIndex = partition(&nums, left, right)

        if k == pivotIndex {
            return nums[k]
        } else if k < pivotIndex {
            return quickSelect(&nums, left, pivotIndex - 1, k)
        } else {
            return quickSelect(&nums, pivotIndex + 1, right, k)
        }
    }

    //就是这个查找中枢的算法略有不同
    func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        let pivot = nums[right]
        var i = left

        
        for j in left..<right {
            if nums[j] <= pivot {
                nums.swapAt(i, j)
                i += 1
            }
        }
// 都是和right的值比较的  所以right 的值 就是那个中枢值
        //然后 理解i的作用 他就是 比right小的区域或者个数
        nums.swapAt(i, right)
        return i
    }
    
    /*
     讲解

         1.    函数 findKthLargest:
         •    这是主函数，接受一个整数数组 nums 和一个整数 k。
         •    它首先将 nums 复制一份（因为 quickSelect 会对数组进行修改）。
         •    然后调用 quickSelect 方法，并将 nums.count - k 作为参数传递，这是因为我们在数组中寻找的是第 k 大的元素，而 quickSelect 寻找的是第 k 小的元素。
         2.    函数 quickSelect:
         •    这是实现快速选择算法的递归函数。
         •    它首先检查 left 是否等于 right，如果相等，表示数组只有一个元素，直接返回该元素。
         •    否则，调用 partition 函数获取 pivotIndex。
         •    然后检查 k 是否等于 pivotIndex，如果相等，说明找到了第 k 大的元素，返回该元素。
         •    如果 k 小于 pivotIndex，在左子数组中继续查找。
         •    如果 k 大于 pivotIndex，在右子数组中继续查找。
         3.    函数 partition:
         •    这是实现快速排序中分区操作的函数。
         •    它选择数组的最后一个元素作为 pivot（基准点）。
         •    然后遍历数组，将小于等于 pivot 的元素移到 pivot 的左侧，大于 pivot 的元素移到右侧。
         •    最后，将 pivot 放在正确的位置上，并返回 pivot 的索引。
     */
    
    //爬楼梯
    func climbStairs(_ n: Int) -> Int {

        if n < 2 {
            return n
        }
        
        var dp = Array.init(repeating: 0, count: n + 1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2
        if n <= 2 {
            return dp[n]
        }
        for i in 3...n {
            dp[i] = dp[i-1] + dp[i-2]
        }

        return dp[n]

    }
    
    /*
     打家劫舍
     你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

     给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     */
    func rob(_ nums: [Int]) -> Int {
        
        //dp[i] 偷到i家时最大的值
        //不能连续偷，所以对于每一间房屋i，要么偷i加上dp[i-2] 要么i这家不偷，仍然是dp[i-1]
        
        if nums.isEmpty {
            return 0
        }
        
        if nums.count == 1 {
            return nums[0]
        }
        //肯定大于一家 nums[1]有值 不越界
        var dp = Array.init(repeating: 0, count: nums.count)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in 2..<nums.count {
            dp[i] = max((nums[i] + dp[i-2]),dp[i-1])
        }
        return dp.last!
    }
    
    
    /*
     零钱兑换
     给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

     计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

     你可以认为每种硬币的数量是无限的
     */
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        //dp[i]代表 凑成 零钱i  所需要的最少硬币数
        //dp[i]代表 凑成 零钱i  所需要的最少硬币数
        //dp[i]代表 凑成 零钱i  所需要的最少硬币数
        //我们要遍历的是零钱amount
        if coins.isEmpty {
            return 0
        }
        
        if amount == 0 {
            return 0
        }
        
        //根据dp定义  要找 dp[amount] 所以数量多创建一个 比如5元最多需要 5个一元  所以初始值设置个大于5的 amount + 1即可
        //对于 5元来说  遍历coins 比如coin有个1元  那么 就看 5 -1 4元需要最少得数量 然后加一即可
        var dp = Array.init(repeating: amount + 1, count: amount + 1)
        dp[0] = 0
        //swift  1...0会越界
        for i in 1...amount {
            for coin in coins {
                if i >= coin {
                    dp[i] = min(dp[i], dp[i-coin] + 1)
                }
            }
        }
        //最后要检查
        let res = dp[amount] == amount + 1 ? -1 : dp[amount]
        return res
    }
    
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        let n = s.count
        var dp = Array(repeating: false, count: n + 1)
        dp[0] = true
        
        let sArray = Array(s) // 将字符串转换为字符数组，便于索引
        let wordSet = Set(wordDict) // 使用Set以便于快速查找
        
        for i in 1...n {
            print("-----")
            for j in 0..<i {
                let subStr = String(sArray[j..<i])
                print("\(j) \(dp[j]) \(subStr)")
                if dp[j] && wordSet.contains(subStr) {
                    print("✅✅✅")
                    dp[i] = true
                    break
                }
            }
        }
        
        return dp[n]
    }
    
    
    /*
     给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
     子数组
     （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。请使用swift给出解释
     
     好的，我们可以通过动态规划来解决这个问题。这个问题的核心在于处理包含负数的情况，因为负数乘积有可能变成正数，从而影响最大乘积的计算。

     我们需要维护两个变量来解决这个问题：

         1.    maxProd：到目前为止的最大乘积。
         2.    minProd：到目前为止的最小乘积（因为负数的存在，最小乘积可能通过乘以负数变成最大乘积）。

     具体步骤：

         1.    初始化 maxProd 和 minProd 为数组的第一个元素，同时初始化 result 为数组的第一个元素，表示当前找到的最大乘积。
         2.    从数组的第二个元素开始遍历，对于每一个元素 num：
         •    如果 num 为负数，则交换 maxProd 和 minProd，因为负数会使最大值和最小值互换。
         •    更新 maxProd 为 max(num, maxProd * num)，即当前元素自身或当前元素乘以之前的最大乘积。
         •    更新 minProd 为 min(num, minProd * num)，即当前元素自身或当前元素乘以之前的最小乘积。
         •    更新 result 为 max(result, maxProd)，即目前为止的最大乘积。
         3.    遍历结束后，result 即为所求的最大乘积。
     
     */
    
    func maxProduct(_ nums: [Int]) -> Int {
        // 初始化maxProd, minProd和result为数组的第一个元素
        var maxProd = nums[0]
        var minProd = nums[0]
        var result = nums[0]

        // 从数组的第二个元素开始遍历
        for i in 1..<nums.count {
            let num = nums[i]
            
            // 如果当前元素是负数，交换maxProd和minProd
            if num < 0 {
                swap(&maxProd, &minProd)
            }
            
            // 更新maxProd和minProd
            maxProd = max(num, maxProd * num)
            minProd = min(num, minProd * num)
            
            // 更新结果
            result = max(result, maxProd)
        }

        return result
    }
    
    /*
     给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     思路：

         1.    计算总和：
     如果数组的总和 sum 不是偶数，则无法将数组分成两个和相等的子集，直接返回 false。
         2.    目标子集和：
     目标子集的和应为 sum / 2，即我们需要找出一个子集，使其和等于 sum / 2。
         3.    动态规划数组：
     使用一个一维布尔数组 dp，其中 dp[i] 表示是否存在和为 i 的子集。
         •    初始化 dp[0] 为 true，因为和为 0 的子集总是存在（空子集）。
         •    遍历数组中的每一个数 num，从后向前更新 dp 数组，以避免重复使用同一个数：
     
     代码解释：

         1.    计算总和并检查奇偶性：
         •    使用 reduce 方法计算数组的总和 sum。
         •    如果 sum 不是偶数，返回 false。
         2.    初始化动态规划数组：
         •    target 为 sum / 2。
         •    初始化 dp 数组，长度为 target + 1，所有元素初始化为 false。
         •    dp[0] 设置为 true，表示和为 0 的子集是存在的。
         3.    更新动态规划数组：
         •    对于数组中的每一个数 num，从 target 向 num 反向遍历更新 dp 数组。
         4.    返回结果：
         •    检查 dp[target]，如果为 true，则存在和为 target 的子集，返回 true；否则返回 false。
     */
    //nums = [1,5,11,5]   target = 11
    func canPartition(_ nums: [Int]) -> Bool {
        let sum = nums.reduce(0, +)
        
        // 如果总和不是偶数，无法分割成两个和相等的子集
        if sum % 2 != 0 {
            return false
        }
        
        let target = sum / 2
        var dp = [Bool](repeating: false, count: target + 1)
        dp[0] = true
        
        for num in nums {
            print("num:\(num)")
            for i in stride(from: target, through: num, by: -1) {
                print("i:\(i)")
                print(dp[i])
                dp[i] = dp[i] || dp[i - num]
            }
        }
        
        return dp[target]
    }

    //1143. 最长公共子序列  时间会超限制
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let len1 = text1.count
        let len2 = text2.count
            //想像二维矩阵解析
            //text1竖向行  text2横向列
        var dp = Array.init(repeating:(Array(repeating: 0, count: len2 + 1)), count: len1 + 1)
        let s1_start = text1.startIndex
        let s2_start = text2.startIndex
        for i in 1...len1 {
            for j in 1...len2 {
                let char1 = text1[text1.index(s1_start, offsetBy: i-1)]
                let char2 = text2[text2.index(s2_start, offsetBy: j-1)]
                if char1 == char2 {
                    dp[i][j] = dp[i-1][j-1] + 1
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                }
            }
        }
        
        return dp[len1][len2]
    }
    
    //最长回文序列的长度
    func longestPalindromeSubseq(_ s: String) -> Int {
        //抽象成一个方阵 m * m（行列记为ij） 从中间位置开始 扩散遍历
        //dp[i][j] 代表子串s[i..j]中最长回文子串的长度
        //方阵左上到右下的斜线是1  左下半部分就是0,因为i>j  串的起始位置大于结束位置 不存在 就是0,
        //只需要在右上部分找答案  i < j的子串中
        let n = s.count
        if n == 0 {
            return 0
        } else if n == 1 {
            return 1
        }
        //s[i] == s[j] 那么dp[i][j] = dp[i+1][j-1] + 2 (里面的那一段加上2)
        //不相等 就是 max（dp[i][j-1],dp[i+1][j]）  ij分别放到s[i+1..j-1]中
        var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
        
        for i in 0..<n {
            dp[i][i] = 1
        }
        //swift  这样遍历 n<2的话 会crash
        //行倒着网上遍历 然后从中间位置往后走
        for i in (0...n-2).reversed() {
            for j in i+1...n-1 {//找规律 中间位置后面一个 往后走
                if s[s.index(s.startIndex, offsetBy: i)] == s[s.index(s.startIndex, offsetBy: j)] {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                }
            }
        }
        
        
        return dp[0][n-1]
        
    }
    
    //最长回文子串
    
    //字母异位词分组
    /*
     遍历这个数组，操作的对象就是每个字符串。
     统计每一个字符和出现的次数，排序构成一个字符串做一个字典的key 比如etce，组合成c1e2t1作为key
     然后value就是一个数组，存放这个的字符串。下一次判断有没有同样的key 有就是符合条件的 直接放入
     */
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        
        
        
        return []
    }
    
    func groupAnagrams1(_ strs: [String]) -> [[String]] {
        var strDic = [String:[String]]()
        for str in strs {
            let sortedStr = String(str.sorted())
            if let _ = strDic[sortedStr] {
                var res = strDic[sortedStr]!
                res.append(str)
                strDic[sortedStr] = res
            } else {
                var res = [str]
                strDic[sortedStr] = res
            }
        }
        
        //这竟然是一个类型。。。集合类型 干嘛不是直接一个数组？
//        let values = strDic.values
        
        return Array(strDic.values)
    }
    
    //128. 最长连续序列
    //要解决这个问题，可以使用哈希集（HashSet）来记录数组中的所有数字。然后，通过迭代哈希集中的每个数字，检查其作为序列起点的可能性，进而找到最长的连续序列。这种方法的时间复杂度是 O(n)，虽然循环嵌套 但是因为每个数字最多会被处理两次：一次插入哈希集，一次作为起点检查。
    //其实没有什么特别的
    /*对于每个数字，只有当它不是某个序列的中间数字时（即 num - 1 不存在于集合中），才开始计算以它为起点的序列长度。
    这样可以确保每个序列只会从最小的起始数字开始计算一次，避免重复计算。
     */
    func longestConsecutive(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        var res = 0
        //转成set遍历有重复数字的怎么办？
        var numSet = Set(nums)//题目无序,转成set效率高
        for num in numSet {
            if numSet.contains(num-1) == false {
                var currentNum = num
                var len = 1
                while numSet.contains(currentNum + 1) {
                    currentNum = currentNum + 1
                    len = len + 1
                }
                res = max(len, res)
            }
        }
        return res
    }
    
    //三数之和
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.isEmpty {return [[Int]()]}
            //排序
            var nums = nums.sorted()
            var res = [[Int]]()
        
        var lastNum = nums.first!
        //swift循环时不能对i操作？只能记录跳过去
            for i in 0..<nums.count {
                if i != 0 && lastNum == nums[i] {
                    continue
                }
                var twores = self.twoSum(nums, i + 1, -(nums[i]))
                for tmp in twores {
                    var tmp = tmp
                    tmp.append(nums[i])
                    res.append(tmp)
                }
                
                lastNum = nums[i]
                
            }
            return res
        }

    //排好序的nums
        func twoSum(_ nums: [Int], _ left: Int, _ target: Int) -> [[Int]] {
            var right = nums.count - 1
            var res = [[Int]]()
            var left = left
            //判断越界
            while left < right {
                let sum = nums[left] + nums[right]
                if sum < target {
                    left = left + 1
                } else if sum > target {
                    right = right - 1
                } else {
                    var tmp = [Int]()
                    let lnum = nums[left]
                    let rnum = nums[right]
                    tmp.append(lnum)
                    tmp.append(rnum)
                    res.append(tmp)
                    while left < right, lnum == nums[left] {
                        left = left + 1
                    }
                    while left < right, rnum == nums[right] {
                        right = right - 1
                    }
                }
            }
            return res
        }
    
    //148. 排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    //归并 看k神图解 找到中间节点 分开分别排序 然后递归返回的时候 两部分排序
        //递归复杂度归并的时间复杂度O(nlogn) 空间递归栈空间O(logn)
        func sortList(_ head: ListNode?) -> ListNode? {
            //必须判断head?.next == nil  否则middle永远有值了 死循环
            if head == nil || head?.next == nil {
                return head
            }
            
            //有个题目是找中间节点 抽成一个单独方法
            var middle = middleNode(head)
            var rightHead = middle?.next
            //断开链表
            middle?.next = nil
            
            var leftPart = sortList(head)
            var rightPart = sortList(rightHead)
            //合并这俩链表
            var node = Merge(leftPart, rightPart)
            return node
        }
    
    //876. 链表的中间结点
    //这里就是注意节点返回的是靠前还是靠后的  偶数奇数不一样
    func middleNode(_ head: ListNode?) -> ListNode? {
        if head == nil {
            return head
        }
        
        var fast = head?.next
        var slow = head
        //一开始就让fast比slow快一步 那么偶数时 slow是靠前的那个节点
        //a->b->c->d  返回b
        while fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }
        
        return slow
        
    }
    //合并链表
    func Merge ( _ pHead1: ListNode?,  _ pHead2: ListNode?) -> ListNode? {
            // write code here
        //直接先搞个假的head
        let head = ListNode.init(0)
        var cur: ListNode? = head
        var p1 = pHead1, p2 = pHead2
        while p1 != nil && p2 != nil {
            if (p1?.val ?? 0) < (p2?.val ?? 0) {
                cur?.next = p1
                p1 = p1?.next
            } else {
                cur?.next = p2
                p2 = p2?.next
            }
            cur = cur?.next
        }
        if p1 == nil {
            cur?.next = p2
        }
        if p2 == nil {
            cur?.next = p1
        }
        //注意head的假头 返回 next
        return head.next
    }
    
    // 2、两数相加
    /*给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
    
    请你将两个数相加，并以相同形式返回一个表示和的链表。

    你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     
     */
    //模拟过程
        func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
            var p1 = l1
            var p2 = l2
            var tmp = 0
            var head: ListNode = ListNode()
            var p:ListNode? = head
            while p1 != nil, p2 != nil {
                
                let v1 = p1?.val ?? 0
                let v2 = p2?.val ?? 0
                let v = (v1 + v2 + tmp) % 10
                tmp = (v1 + v2 + tmp) / 10

                let node = ListNode.init(v)
                p?.next = node
                p = p?.next

                p1 = p1?.next
                p2 = p2?.next
            }
            //注意不等长时 剩余的部分
            while p1 != nil {
                let v1 = p1?.val ?? 0
                let v2 =  0
                let v = (v1 + v2 + tmp) % 10
                tmp = (v1 + v2 + tmp) / 10

                let node = ListNode.init(v)
                p?.next = node
                p = p?.next

                p1 = p1?.next
            }

            while p2 != nil {
                let v2 = p2?.val ?? 0
                let v1 =  0
                let v = (v1 + v2 + tmp) % 10
                tmp = (v1 + v2 + tmp) / 10

                let node = ListNode.init(v)
                p?.next = node
                p = p?.next

                p2 = p2?.next
            }
    //注意剩余的进位
            if tmp == 1 {
                let node = ListNode.init(1)
                p?.next = node
            }

            return head.next
        }

    
}
